import java.util.*;
public class Mylist <E>
{
    class MyListIterator implements Iterator<E>
	{
	    Node<E> cur = head;
		boolean dir;
		public MyListIterator(){};
		public MyListIterator(boolean dir)
		{
		    this.dir = dir;
			cur = dir ? head : tail;
		};
		public boolean hasNext()
		{
		    return cur !=null;
		}
		public E next(){
		    E obj = cur.data;
			cur = dir ? cur.next : cur.previous;
			return obj;
		}
		public void remove(){}
	}
	public Iterator<E> iterator()
	{
		return iterator(true);
	}
	public Iterator<E> iterator(boolean direction)
	{
		return new MyListIterator(direction);
	}
	protected int count;
	protected Node<E> head,tail;
	public Mylist()
	{
		count = 0;
		head = tail = null;
	}
	public boolean empty () 
	{
		return count ==0;
	}
	public int size()
	{
		return count;
	}
	Mylist<E> insert (E obj, int pos)
	{
		Node<E> nn=new Node<E>(obj);
		if (count==0)
		{
			head=tail=nn;
		}
		else if(pos<1)
		{
			//insert in the front
			nn.next = head;
			head.previous = nn;
			head = nn;
		}
		else if(pos>=count)
		{
			//add the new node to the end
			tail.next = nn;
			nn.previous = tail;
			 tail = nn;
		}
		else
		{
			//add new node in the middle
			Node<E> cur = head;
			for (int i =1;i<pos;i++)
				cur = cur.next;
				nn.previous = cur;
				nn.next = cur.next;
				cur.next = nn;
				nn.next.previous=nn;
			
		}
		count++;
		return this;
	}
	E remove(int pos)
	{
        E obj = null;
		
		if(count <1 || pos >=count ||pos<1)return null;
		else if(count==1)
		{
			obj=head.data;
			head=tail=null;
		}
		else if(pos==1)
		{
			obj=head.data;
			head=head.next;
			head.previous.next=null;
			head.previous=null;
		}
	        else if(pos == count-1)
		{
			obj=tail.data;
			tail=tail.previous;
			tail.next.previous=null;
			tail.next=null;
		}
		else
		{
		    Node<E> cur = head.next;
			for(int i=1;i<pos;i++)
			{
				cur=cur.next;
			}
			obj=cur.data;
			cur.previous.next=cur.next;
			cur.next.previous=cur.previous;
			cur.next=cur.previous=null;
		}
		count--;
		return obj;
	}
}


class Node<E>
{
	E data;
	Node<E> previous,next;
	public Node(E obj)
	{
		data=obj;
		previous=next=null;
	}
}
